package org.hot100_5.leetcode139;

import java.util.List;

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        //dp[i]表示前i个字符的拼接情况
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        for (int i = 1; i <=n; i++) {
            for(String str:wordDict){
                if (i>=str.length() && dp[i-str.length()]){
                    String substring = s.substring(i - str.length(), i);
                    if (substring.equals(str)){
                        dp[i]=true;
                        break;
                    }
                }
            }
        }

        return dp[n];
    }
}
